package algorithm.bitcalculate;

/**
 * 使用位运算解决N皇后问题.
 * </p>
 * 
 * <pre>
 * 八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8
 * 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：
 * 这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。
 *
 * @see (可填，引用或参考其他类型资源，如: {@link java.util.Properties}).
 * @author zhangbo
 * @since 1.0.0
 */
public class NQueen {
    public int dfs(int max, int row, int ld, int rd) {
        if (row == max) {
            // find one
            return 1;
        }
        int pos = max & (~(row | ld | rd));
        // System.out.println("row:" + toBinaryString(row));
        // System.out.println("ld: " + toBinaryString(ld));
        // System.out.println("rd: " + toBinaryString(rd));
        // System.out.println("po: " + toBinaryString(pos));
        // System.out.println();
        int sum = 0;
        while (pos != 0) {
            int temp = pos & (-pos);
            sum += dfs(max, (row | temp), ((ld | temp) << 1), ((rd | temp) >> 1));
            pos = pos - temp;
        }
        return sum;
    }

    public void execute(int n) {
        long before = System.currentTimeMillis();
        int max = (1 << n) - 1;
        System.out.println(String.format("the result of %s queen is %s", n, dfs(max, 0, 0, 0)));
        long after = System.currentTimeMillis();
        System.out.println("cost time : " + (after - before) + "ms");
    }

    public static void main(String[] args) {
        NQueen run = new NQueen();
        run.execute(8);
    }

    public static String toBinaryString(int a) {
        String str = "";
        for (int i = 0; i < 32; i++) {

            int t = (a & 0x80000000 >>> i) >>> (31 - i);

            str += String.valueOf(t);
        }
        return str;
    }
}
